The present invention relates to an alignment network for use in a parallel data processing environment. More particularly, the present invention finds application in unscrambing a d-ordered vector having its elements stored a distance d apart from each other in the parallel memory modules of a parallel data processor.
In the prior art, as disclosed in U.S. patent application, Ser. No. 682,526, now U.S. Pat. No. 4,051,551, filed May 3, 1976, in the names of D. H. Lawrie and C. R. Vora and assigned to the assignee of the present invention, there is described a cross-bar network for transferring and aligning data between a set of parallel memory modules and a set of parallel processors. The cross-bar network so disclosed is relatively easy to program or control; however, it is also relatively costly in components requiring N.sup.2 elementary elements to transmit data through wherein N is the number of parallel memory modules storing data to be aligned.
Other prior art networks require fewer components but present difficult control problems. Typical of this type of alignment network is the Benes network requiring only 2N log.sub.2 N elements, see Benes, V. E., "Optimal Rearrangeable Multi-stage Connecting Networks, Part 2," Bell System Technical Journal Vol. 43, 1964, p. 1641.
Still other prior art alignment networks require fewer components than the cross-bar network and are not too difficult to control or program, but these require multiple data flow transitions cycling through a single alignment layer thereby increasing the time required for data to pass through the network; see Roger C. Swanson, "Interconnections for Parallel Memories to Unscramble p-ordered Vectors", IEEE trans. Computers, November 1974. Swanson's "p-ordered vectors" corresponds to the "d-ordered vector" terminology used herein.
Therefore, it is an object of the present invention to provide an alignment network for d-ordered vectors requiring fewer components than a cross-bar network and yet being easy to control.
It is yet another object of the invention to provide alignment for d-ordered vectors while requiring only a single pass through any of the elements used for alignment.